#include "Double_Link_Lis.h"
#include "Double_Link_Lis.h"
#include "Double_Link_Lis.h"
#include "Double_Link_Lis.h"


// 双向链表的创建
Double_Link_List* init_double_link_list()
{

    // 创建头结点
    Double_Link_List * L = (Double_Link_List *)malloc(sizeof(Double_Link_List));
    // 安全判断
    if (NULL == L)
    {
       rintf("创建失败\n");
        return NULL;
    }
    // 进行指向初始化
    L->next = NULL;    // 这一步一定要做 不然链表无法判空
//  有头节点的时候  L->next = NULL; 为空
//  无头节点的时候  L = NULL; 为空
    return L;
}

// 双向链表的插入
void insert_double_node(Double_Link_List* list, Element_data data, int index)
{
    // 安全判断
    if (NULL == list)
    {
        printf("空间不存在\n");
        return ;
    }
    // 创建新结点
    Double_Node * new_node = (Double_Node *)malloc(sizeof(Double_Node));
    new_node->data = data;
    // 安全判断
    if (NULL == new_node)
    {
        printf("创建失败\n");
        return ;
    }
    // 头插

    if (index == 0 || NULL == list->next)
    {
        // 将新结点的next 指向 头结点的next
        new_node->next = list->next;
        // 将新结点的prev 指向 NULL
        new_node->prev = NULL;
        // 将头结点指向新结点
        list->next = new_node;
        if (NULL != list->next->next)
        {
            // 如果 是 1 元素插入模式则 需要将后继结点的前指针指向 下标 0 元素
            new_node->next->prev = new_node;
        }
        return ;
    }
    
    // 中间插入
        // 创建一个新结点
    Double_Node * new_ptr = list->next;

    for (size_t i = 0; i < index - 1 && NULL != new_ptr->next ; i++)
    {
        // 遍历链表
        new_ptr = new_ptr->next;
    }

    // 开始中间插入

    // 1 将新结点的 next 指向 p 的next 
    new_node->next = new_ptr->next;
    // 2 将新结点的 prev 指向 p
    new_node->prev = new_ptr;
    // 3 将后继结点的prev 指向 new_node
    if (NULL != new_node->next)
    {
        new_node->next->prev = new_node;
    }
    // 4 将new_ptr 的 next 指向 new_node
    new_ptr->next = new_node;

    return ;
}

// 双向链表的删除    我这个删除无返回，你们需要写 带返回的
void delete_double_node(Double_Link_List* list, int index)
{
    // 安全判断
    if (NULL == list)
    {
        printf("空间不存在\n");
        return ;
    }
    if (NULL == list->next)
    {
        printf("链表内无结点\n");
        return ;
    }
    Double_Node * new_p = list->next;

    // 头删
    if (index == 0)
    {
        // 1 头结点指向 new_p 的next 
        list->next = new_p->next;
        // 2 将下一个结点 的 prev 指向 null
        new_p->next->prev = NULL;
        // 3 释放空间
        free(new_p);
        return ;
    }

    // 中间删除
    for (size_t i = 0; i < index - 1 && NULL != new_p->next ; i++)
    {
        // 遍历链表
        new_p = new_p->next;
    }

    Double_Node * new_q = new_p->next;

    // 开始删除
    if (NULL == new_p || NULL == new_p->next)
    {
        printf("删除的空间为空\n");
        return ;
    }
    
    // 1 将 p 的next 指向 q的next
    new_p->next = new_q->next;
    // 2 将 q 的next 的prev 指向 p
    if (NULL != new_q->next)
    {
        new_q->next->prev = new_p;
    }
    
    // 3 释放 new_q
    free(new_q);
    return ;
}



// 双向链表的判空
/*
    返回值  为空 则返回     true	1
    返回值  不为空 则返回   false	0
*/
bool is_empty_double_link_list(Double_Link_List* list)
{
    if (NULL == list->next) 
    {   
        // 条件成立判定为空
        return 1;
    }
    return 0;
}

// 双向链表的清空
void clear_double_link_list(Double_Link_List* list)
{
    // 安全判断
    if (NULL == list)
    {
        printf("空间不存在\n");
        return ;
    }
    if (NULL == list->next)
    {
        printf("表已经为空\n");
        return ;
    }

    Double_Node * new_p = list->next;
    Double_Node * new_q = list->next;
    for ( ; NULL != new_p ; new_p = new_q)
    {
        new_q = new_p->next;
        free(new_p);
    }
    printf("链表已经释放完成");
}

// 双向链表的合并
Double_Link_List* merge_double_link_lists(Double_Link_List* list1, Double_Link_List* list2)
{
    if (NULL == list1)
    {
        printf("list1 空间不存在\n");
        return NULL;
    }
    if (NULL == list2)
    {
        printf("list2 空间不存在\n");
        return NULL;
    }

    Double_Link_List * list3 = init_double_link_list();
    size_t i = 0;
    Double_Node * new_pre = list1->next;
    for (; NULL != new_pre ; i++ , new_pre = new_pre->next)
    {
        insert_double_node( list3 , new_pre->data , i);
    }

    new_pre = list2->next;
    for (; NULL != new_pre ; i++ , new_pre = new_pre->next)
    {
        insert_double_node( list3 , new_pre->data , i);
    }

    return list3;

}



// 双向链表的遍历
void print_double_link_list(Double_Link_List* list)
{
    // 安全判断
    if (NULL == list)
    {
        printf("空间不存在\n");
        return ;
    }
    
    if (NULL == list->next)
    {
        printf("内部无数据不能遍历打印\n");
        return ;
    }

    Double_Node * ptr = list->next;

    for ( ; ptr != NULL ; ptr = ptr->next )
    {
        printf("姓名 %s\t性别 %s\t年龄 %d\t学号 %d\t成绩 %d\n" , 
        ptr->data.name , 
        ptr->data.sex , 
        ptr->data.age , 
        ptr->data.id ,
        ptr->data.sco);
        
    }
    
}


// 双向链表的销毁
void free_double_link_list(Double_Link_List * list)
{
    if (NULL == list)
    {
        printf("空间不存在\n");
        return ;
    }
    if (NULL == list->next)
    {
        free(list);
        printf("没有后续结点 , 已经清除头节点\n");
        return ;
    }
    // 1、新建一个 new_p  new_q
    Double_Node * new_p = list->next;
    Double_Node * new_q = NULL;

    for ( ; NULL != new_p ; new_p = new_q)
    {
        new_q = new_p->next;
        free(new_p);
    }
    list->next = NULL;
    free(list);
    list = NULL;
}
void _free_double_link_list(Double_Link_List ** list)
{
    
    if (NULL == (*list))
    {
        printf("空间不存在\n");
        return ;
    }
    if (NULL == (*list)->next)
    {
        free(*list);
        *list = NULL;
        printf("没有后续结点 , 已经清除头节点\n");
        return ;
    }
   
    // 1、新建一个 new_p  new_q
    Double_Node * new_p = (*list)->next;
    Double_Node * new_q = NULL;

    for ( ; NULL != new_p ; new_p = new_q)
    {
        new_q = new_p->next;
        free(new_p);
    }

    (*list)->next = NULL;
    free(*list);
    *list = NULL;
}

